A priority queue is a queue in which queue elements, items that each represent a task to be served, are stored and serviced according to different levels of priority that are assigned to different ones of the queue elements. There are a number of known ways of managing priority queues. The most obvious way is to assign a separate queue to each priority class and service each queue separately according to its priority class. This method has serious performance limitations when there are more than just a few priority classes. Algorithms for managing priority queues are described in many text books, such as DATA STRUCTURES and ALGORITHMS, Aho et al, Addison-Wesley, 1983, Section 4.10-4.11; and ALGORITHMS, Sedgewick, Addison-Wesley, 1983, Chapter 11.
Sedgewick describes the conventional data structure, called a heap, heretofore considered the most efficient for a priority queue able to handle an unlimited number of priority classes. A heap is a tree structure with each node of the tree having at most two child nodes. Nodes represent transactions and each has a priority class. Nodes are added at the first available position progressing left to right and top to bottom through the heap. The heap must follow the rule that a parent node can have a priority class which must be equal to or greater than the priorities of its children. When a node is added to the first available position left to right and top to bottom, the above rule respecting the priorities of parents and children may be broken. If this is true after a node is added, the algorithm then exchanges the added node with its parent. If the rule is still broken with respect to the parent and its parent, the exchange is repeated for these two nodes, and so on up the tree, until all nodes satisfy the rule. It can be shown that this heap algorithm performs in O(Log N) time, where N represents the number of nodes of the heap. In many real implementations of priority queues and heaps, the number of priority classes can become quite large, often in the hundreds. In such situations, it is often true that the processing time for managing priority queues and heaps still represents too much of system resources. Thus, a need exists to further improve the operation of priority queues.